//求二叉搜索树任意两个节点值的最小值
//可以先用中序遍历求出先序数组，然后求相邻元素差的最小值
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
#include <iostream>
#include <vector>
#include <algorithm>
using std::min;
using std::vector;
//递归
void traversal(TreeNode* root,vector<int>& vec){
    if(!root) return;
    traversal(root->left,vec);
    vec.push_back(root->val);
    traversal(root->right,vec);
}
int getMinimumDifference(TreeNode* root) {
    vector<int> nums;
    traversal(root,nums);
    int reslut=INT32_MAX;
    for(int i=0;i<nums.size()-1;i++){
        reslut=min(reslut,nums[i+1]-nums[i]);
    }
    return reslut;
}

//不使用新数列的方法
//和检验搜索二叉树一样，使用一个pre记录上一个节点
int res=INT32_MAX;
TreeNode* pre=nullptr;
int getMinimumDifference(TreeNode* root) {
    if(!root) return 0;
    getMinimumDifference(root->left);
    
    if(pre) res=min(res,root->val-pre->val);

    pre=root;   //记录上一个节点
    getMinimumDifference(root->right);
    return res;
}


#include <stack>
using std::stack;
//迭代法，也是使用一个pre记录上一个节点
int getMinimumDifference(TreeNode* root) {
    if(!root) return 0;
    stack<TreeNode*> st;
    int res=INT32_MAX;
    TreeNode* cur=root;
    TreeNode* pre=nullptr;
    while(cur||!st.empty()){
        if(cur){
            st.push(cur);
            cur=cur->left;
        }
        else{
            cur=st.top(); st.pop();
            if(pre) res=min(res,cur->val-pre->val);
            //中
            pre=cur;
            cur=cur->right;
        //右
        }
    }
    return res;
}